The present invention relates to a method of compiling a program written in a logic programming language for computers represented by PROLOG and intends high speed execution of artificial intelligence (AI) programs by a pipelined vector processor or a parallel vector processor.
Representation of a program by a logic programming language is first explained.
In the logic programming language, a proposition in predicate logic (called clause in the logic programming language) is described as follows. EQU bird (swallow). 1 EQU fly(X):-bird(X). 2
The clause 1 means "A swallow is a bird." The clause 2 means "If X is a bird, X flies in the sky." The head name in the clause (bird in 1, and fly in 2) is called a procedure name or predicate name. The set of clauses having the same predicate name is called a procedure or predicate. If the program consists of only the clauses 1 and 2, each of the clauses 1 and 2 is a procedure by itself.
A name whose initial letter is uppercase (X in the above example) represents a logical variable and it represents an unspecified object. On the other hand, a name whose initial letter is lowercase (swallow in the above example) is called a constant and it represents a specific object or number. Unlike a variable in a programming language such as FORTRAN, the value of the logical variable, once it is set, cannot be changed unless failure takes place. That is, assignment in a conventional sense is not allowed.
Assuming that 1 and 2 are given to a logic programming language system as a program, and assuming that the following question 3 is made. The concept "question" corresponds to "main program" in FORTRAN language. EQU ?-fly (swallow). 3
The result of question 3 is true. The question means "Does a swallow fly in the sky?".
The program may be used as follows. EQU ?-fly (Y). 4
The result is Y=swallow. The question 4 means "What flies in the sky?" and fly (swallow) means a swallow flies in the sky" or "It is a swallow that flies in the sky".
The fly (swallow) in the question 3 and the fly(Y) in the question 4 are called procedure calls of procedure "fly". Similarly, the bird (X) in the clause 2 is a procedure call of procedure "bird". The procedure call corresponds to a subroutine call in FORTORAN language.
The attribute that the program whose input and output are exchanged is executable as in question 3 and the question 4 is called bidirectionality (An argument for "fly" is an input in the question 3 and an output in the question 4.) The bidirectionality is one of the characteristics of the logic programming language program.
If the following program 5 is added to 1 and 2, the solution of the question 4 is Y=swallow and Y=hen. (In this case, the procedure "bird" comprises two clauses.) EQU bird (hen). 5
Such a plurality of solutions is also a characteristic of the logic programming language program.
Before the question "?-fly(Y)" is executed, the logical variable Y is unspecified, but it is bound to a constant "swallow" during the execution. When the logical variable is bound to a specific object, it is said "instantiated" and when it is not bound to a specific object, it is said "uninstantiated".
Sequential execution of the logic programming language is now explained.
As an example, a program 200 shown in FIG. 2 is used. The meaning of the program 200 is first explained. Clauses 201-205 mean as follows.
Clause 202 "A swallow is a bird." PA1 Clause 203 "A hen is a bird." PA1 Clause 204 "A penguin cannot fly in the sky." PA1 Clause 205 "A hen cannot fly in the sky."
Procedure bird consists of clauses 201, 202 and 203 and procedure cannot Fly consists of clauses 204 and 205.
Question 206 means "Output all those birds which cannot fly in the sky." More exactly, it means "Output all possible solutions of a logical variable X which meets bird(X) and cannot Fly(X), and if there is no more solution, output "false". The question 206 comprises four procedure calls, "bird(X)", "cannot Fly(X)", "write (X)" and "fail".
FIG. 3 illustrates the sequential execution of question 206. The sequential execution of the logic programming language is explained with reference to FIG. 3. While procedure call "bird" 301 is executed, the logical variable X is uninstantiated. There are three clauses 201-203 which match (unify) "bird(X)" and the first one, clause 201 is selected. As a result, the logical variable X is instantiated to "penguin". Then, the procedure call "cannot Fly" 302 is executed. Since the logical variable X has been instantiated to "penguin", only the clause 204 in the clauses 204-205 matches. Then, the procedure call "write" 303 is executed. Since the logical variable X has been instantiated to the constant "penguin", one solution "penguin" is displayed on an output device. Then, the procedure call "fail" 304 is executed.
Since the procedure "fail" means "Search another solution", another solution of the procedure call "cannot Fly" is searched. This step is called retrial of the procedure "cannot Fly". Since there is no other solution so long as X is instantiated to the constant "penguin", the procedure "cannot Fly" does not return a result to the argument X by the retrial. Accordingly, the state of the logical variable X is restored to that prior to 301, that is, to an uninstantiated state and the procedure "bird" is retrial (305). That is, other solution of the procedure call "bird" is searched. The step to restore the logical variable to its previous value and retry the procedure call is called "backtrack". In the step 305, a solution is found and the logical variable X is instantiated to the constant "swallow". Then, the procedure call "cannot Fly" 306 is executed. Since the logical variable X has been instantiated to the constant "swallow", there is no matchable clause in clauses 204-205. Accordingly, the trial fails, X is reset to the uninstantiated state and the procedure call "bird" is again retried (307).
The steps 307-310 are executed in the same manner as the steps 301-304 and the explanation thereof is omitted. Finally, X is again reset to the uninstantiated state and the procedure "bird" is retried (311). Since there is no other solution, the result to the question 206 is false and the execution is terminated.
A compiling method for generating a program which is sequentially executed is disclosed in "Implementing PROLOG--Compiling Predicate Logic Programs", D.A.I. Research Report No. 39, Department of Artificial Intelligence, University of Edinburgh.
As described in the Japanese Patent Application document 61-65337 (filed on Sept. 7, 1984), in order to materially increase a speed of execution of the logic programming language, a high speed vector operation mechanism of a pipelined vector processor or a parallel vector processor can be used. The vector operation means an operation of the same type to each of vectors or data comprising plural elements of the same type. In a vector operation, a data structure (or array) in which elements are arranged in a continuous area at a constant stride is usually a target of operation. Here, an operation of the same type to each element of a list is also called the vector operation. The vector processor means a processor having vector instructions.
An example of the vector processor is Hitachi S-810. The processor of S-810 is explained with reference to FIG. 4. In S-810, an array data can be processed at a high speed by a pipeline mechanism shown in FIG. 4. For example, data contained in array data 401 on a main memory 421 are sequentially loaded to a vector register 403 by a load pipeline 402. The load pipeline means a hardware for processing the array data which can load the entire array data (or a portion thereof) at a short pitch. The vector register means a large capacity register which can hold the entire array data (or a portion thereof). Data contained in array data 404 are loaded to the vector register 406 by a load pipeline 405, in the same manner as that for 401-403.
When a first element is written into the vector register, it can be immediately read. Accordingly, when first data are written into the vector registers 403 and 406, the processing by a processor 407 is immediately started and the processing is sequentially carried out. A result of the processing is written into a vector register 408. The processor is a pipelined processor designed for array processing and it can process at the same pitch as the vector registers 403 and 406. When a first data is written into the vector register 408, the storing into the array data 410 is immediately started by a store pipeline 409 and the data are sequentially stored.
Since the array data are loaded, processed and stored in the pipeline fashion in the vector processor, the array data can be processed much faster than by a general purpose computer.
The execution method of the logic programming language program in the vector processor is shown in the above JP-A and "High Speed Execution of PROLOG by A Supercomputer" 26th Programming, Symposium Report, pages 47-56, 1985 in Japanese. A method for executing the above example in the vector processor is explained with reference to FIG. 5.
FIG. 5 shows a method for executing the program of FIG. 2 by the vector processor. A procedure call "bird" 501 obtains all the solutions which meet a procedure "bird" to form array data 502. The processing corresponding to the steps 301, 305, 307 and 311 of FIG. 3 is carried out by vector operation, and resulting X is given by array data 502. Accordingly, the array data 502 comprises three constants, "penguin", "swallow" and "hen". The number of elements, "3", is stored at the top of the array data 502. The number of elements is stored at the top of each array data. This data is not regarded as an element of the array. This is also true for the embodiments to be described later. For example, the first element of the array data 502 is not "3" but "penguin", the second element is "swallow" and the third element is "hen".
A procedure call "cannot Fly" 503 reads in the array data 502 and detects all solutions which meet the procedure "cannot Fly" to form array data 504. The step 302 of FIG. 3 is carried out for the element "penguin" of the array data 502, the step 306 of FIG. 3 is carried out for the element "swallow", and the step 308 of FIG. 3 is carried out for the element "hen". Thus, it is determined that X which meets "cannot Fly(X)" is "penguin" and "hen". Array data 504 comprising those two elements is defined. Accordingly, the array data 504 comprises two constants, "penguin" and "hen".
A procedure call "write" 505 reads in the array data 504 and displays all elements thereof on an output device. That is, the steps 303 and 309 of FIG. 3 are carried out. Thus, "penguin" and "hen" are displayed on the output device.
Finally, a procedure call 506 is executed. Since all solutions have been obtained for "bird" 501 and "cannot Fly" 503, the result for the question 201 is false and the execution is terminated.
Prior to the explanation of the problem, a program 600 shown in FIG. 6 is explained.
The program 600 determines square numbers between 0 and 3, inclusive. The square number means a number whose root is an integer. Because 0=0.sup.2 and 1=1.sup.2, the solution is "0" and "1", respectively. The program in FIG. 6 consists of three portions, a question 601, a procedure "root" 602 and a procedure "digit" 603.
In the question 601, the procedure "root" 602 and the procedure "digit" 603 are called to calculate a root and it is printed out. The question 601 comprises four portions, "digit (B)", "root (B, A)", "write (B)" and "fail". The "digit (B)" calls the procedure "digit" by using a logical variable B as an argument. The "root (B, A)" calls the procedure "root" by using the logical variables B and A as arguments. The "write (B)" calls a built-in procedure "write" to print out the value of the logical variable B. The built-in procedure means a procedure which is previously prepared in the logic programming language system and can be used without supplying a processing method by the user. The procedure "fail" is the built-in procedure. In the procedure "fail", the procedures "root (B, A)" and "digit (B)" are retried until all solutions are obtained and "digit (B)", "root (B, A)" and "Write (B)" are repeatedly executed.
The procedure "root" 602 comprises only one clause. The clause 602 comprises a head "root (Y, X)", a body "digit (X), Y is X * X" and an operator ":-". The head indicates a procedure name and an argument. The procedure "root" 602 receives arguments Y and X. In the call of "root" in the query 601, Y=B and X =A. The body of the procedure root 602 comprises two portions, "digit (X)" and "Y is X * X". The portion "digit (X)" calls the procedure "digit" by using the logical variable X as an argument. "Y is X * X" is a built-in procedure in which square of the logical variable X is compared with Y. The portion "digit (X)" is retried when a retry is caused by the procedure call "fail" of the query 601, and different values of arguments are produced.
The procedure "digit" 603 comprises four clauses. After the first clause "digit (1)" has been executed, an argument in the call of "digit" is set to "1". The same is true for the second to the fourth clauses. The program 600 of FIG. 4 has thus been explained.
A problem encountered in executing the program 600 of FIG. 6 in a prior art vector processor is explained, with comparison to the program 200 of FIG. 2.
In the program 200 of FIG. 2, the procedure "bird" produces a different argument for each call and each retry. Thus, the procedure call "cannot Fly (X)" is called plural times (N times). However, in no case, the retrial of the procedure "cannot Fly" successes nor the value is returned to the argument. (In the call, the trial is successed and the value is returned to the argument, or it is failed.) In the execution method of FIG. 5, plural values, that is, "penguin", "swallow" and "hen" are given to array data 502 corresponding to the logical variable X by the execution of "bird" 501, and the elements "penguin" and "hen" produces one solution, respectively, and "swallow" produces no solution. As a result, array data 504 is produced. When each array element before processing corresponds to one or zero array element after processing, the method shown in the above JP-A may be used. It may be readily implemented by combining vector instructions of the vector processor such as S-810.
This is not true for the program 600 of FIG. 6. Because the procedure call "digit (Y)" produces a different argument data by each call and each retrial, the procedure call "digit (X)" is called plural times (N times). Thus, unlike the program 200, a different argument data is produced by each call and each retrial. Accordingly, the second array data having elements of logical variables Y before processing does not match to first array data having elements of argument data X after processing. However, in the conventional vector processor, there is no vector instruction which processes the non-corresponding elements. Accordingly, the program 600 cannot be executed by the method shown in the above JP-A. In the above article (2), procedure "select" in a program which solves a puzzle called N queens problem is cited as an example of generation of plural array elements from each element of the array data, and input data and output data therefor are explained. However, a program for computation is not given.